One aspect typical of a data processing system is operating with lists. Each list is comprised of a number of items. Each item is something to be performed or used by the data processing system. Items are typically processes, data, programs, or subroutines. One way of keeping track of a list is to have a head pointer and a tail pointer for each list. The head pointer points to the first item in the list. The tail pointer points to the last item in the list. In a singly-linked list the first item has a next pointer which points to the next item in the list which is then the second item in the list. The second item has also a next pointer which points at the item which follows next after the second item which is then the third item. The third item similarly has a next pointer which points at the fourth item, and so forth to the last item in the list. The last item also has a next pointer, but since it is the last item, its next pointer is typically null (all zeros).
Another type of list which offers advantages relative to speed of traversing the list is the doubly-linked list. In such a list each item has not only a next pointer but also a back pointer. The back pointer is used to point just ahead in the list. For example, the back pointer of the third item in the list points to the second item while the next pointer of the third item points to the fourth item. The last item's next pointer is still null while its back pointer points to the next-to-last item, assuming of course that the list has more than one item. For the first item in the list the back pointer is null in view of there being no item ahead of it, and the next pointer points to the second item.
During the operation of the data processing system it is desirable to add and delete items from lists. One technique that has been developed in a mainframe data processing system for such an operation for singly-linked lists in an instruction called "compare and swap". The instruction can be used to cause the proper adjustment to the head pointer of the list so that an item can be added or deleted at the head of the list. Before the compare and swap instruction is excuted, however, the address in the head pointer is read and stored. Then if, for example, a new item is to be added, a swap value which can be substituted into the head pointer is prepared. This swap value when so substituted will cause the header pointer to point at the new item. The preparation of the new item includes causing its next pointer to point at the next following item which is the item which is at the head of the list prior to the addition of the new item. After the new item is ready, the stored address is compared to the address in the head pointer to make sure they are still the same. During the preparation of the new item, the list may have been altered causing the next pointer of the preceding item to also have been altered. If the compared addresses are different, the process must start over. If the compared addresses are the same, an address pointing to the new item (the swap value) is inserted into the next pointer of the preceding item, thus effecting the addition of the new item. As previously stated, lists often have tail and head pointers for assisting in keeping track of the lists. Such a compare and swap operation is not effective for adding or deleting at the end of the list even when the list has head and tail pointers. This is because not only the tail pointer must be changed but also the former last item must be changed to point at the new last item. This has not been available. Similarly, insertion and deletion was not available in the middle of a list because the item that is to point at the new item (in the case of a new item being added) may have been moved to a different list. Consequently, the compare test may be passed but the new item would be inserted into the wrong list.